/***************************************************************
*
* DS_ALLOCATOR.H
*
***************************************************************/

#ifndef _DS_ALLOCATOR_H_
#define _DS_ALLOCATOR_H_

//#include "ap\ap_dlstat.h"
#include "ds\ds_vector.h"
#include "ds\ds_ptr_list.h"

#ifndef __PLUGIN__
#define USE_FIXED_ALLOC 1
#else
#define USE_FIXED_ALLOC 0
#endif

#if USE_FIXED_ALLOC
#define dsFIXED_ALLOC(TYPE)         ds::FixedAlloc.Alloc<TYPE>()
#define dsFIXED_ALLOC_1(TYPE, ARG)  ds::FixedAlloc.Alloc<TYPE>(ARG)
#define dsFIXED_FREE(PTR)           ds::FixedAlloc.Free(PTR)
#else
#define dsFIXED_ALLOC(TYPE)         apNEW TYPE()
#define dsFIXED_ALLOC_1(TYPE, ARG)  apNEW TYPE(ARG)
#define dsFIXED_FREE(PTR)           delete PTR
#endif

//
// Fixed size allocator
//
template <class T>
class dsNODE_CACHE {
public:
   dsNODE_CACHE  (/*AP_CL_DECL*/);
   ~dsNODE_CACHE (void) { Term(); }

   BOOL Init     (int _nNode);
   void Term     (void);

   void Free     (void);

   T*   GetEmpty (void);
   void Release  (T * pNode) { freeNodeList.PushBack(pNode); }

   void Swap(dsNODE_CACHE<T> & p)
   {
      dsSwap(nNode, p.nNode);
      nodeList.Swap(p.nodeList);
      freeNodeList.Swap(p.freeNodeList);
   }

private:
   dsNODE_CACHE(const dsNODE_CACHE & p);
   void operator = (const dsNODE_CACHE & p);

   BOOL AddNodes (void);

private:
   typedef ds::PTR_LIST<T> FREE_LIST;
   int                nNode;
   dsVECTOR<T*>       nodeList;
   FREE_LIST         freeNodeList;

#ifdef AP_USE_MEM_STAT
   apCL    __cl;
#endif
};

template <class T>
class dsNODE_CACHE_ALLOCATOR : public dsNODE_CACHE<T> {
public:
   dsNODE_CACHE_ALLOCATOR (/*AP_CL_DECL*/) : dsNODE_CACHE<T>(/*cl*/) {}

   inline T*   Alloc    (void)     { return dsNODE_CACHE<T>::GetEmpty();  }
   inline void Delete   (T *pNode) { Release(pNode);     }

private:
   dsNODE_CACHE_ALLOCATOR(const dsNODE_CACHE_ALLOCATOR &);
   void operator = (const dsNODE_CACHE_ALLOCATOR &);
};

template <class T>
class dsNODE_CACHE_REF_ALLOCATOR {
   dsNODE_CACHE<T> *pNodeCache;

public:
   dsNODE_CACHE_REF_ALLOCATOR    (void) : pNodeCache(NULL) {}
   dsNODE_CACHE_REF_ALLOCATOR    (dsNODE_CACHE<T> *_pNodeCache) : pNodeCache(_pNodeCache) {}

   inline void           SetNodeCache   (dsNODE_CACHE<T> *_pNodeCache) { pNodeCache = _pNodeCache; }

   inline T*             Alloc          (void)     { return pNodeCache->GetEmpty();  }
   inline void           Delete         (T * pNode) { pNodeCache->Release(pNode);     }
};

template <class T>
class dsNEW_ALLOCATOR {
public:
   inline T *            Alloc          (void) { return apNEW T; }
   inline void           Delete         (T * ptr) { delete ptr; }
};

namespace ds {

template <class T>
struct ALLOC_DELETE_POLICY {
   T * Alloc(dsVECTOR<T *> & usedNodes) {
      T * res = NULL;
      if (!freeNodes.IsEmpty()) {
         res = freeNodes.Back();
         freeNodes.PopBack();
      } else {
         res = apNEW T();
      }
   }

   void Delete(T * ptr, dsVECTOR<T *> & usedNodes) {
      int index = ds::FindNonSorted(usedNodes, ptr);
      STRONG_ASSERT(index != -1);

      usedNodes.EraseNonSorted(index);
      freeNodes += ptr;
   }

   ~ALLOC_DELETE_POLICY(void)
   { Free(); }

   void Free(void) {
      for (int i = 0; i < freeNodes.Length(); ++i) {
         delete freeNodes[i];
      }
      freeNodes.Clear();
      freeNodes.Free();
   }

   dsVECTOR<T *> freeNodes;
};

template <class T, template <class> class ALLOC_POLICY = ALLOC_DELETE_POLICY>
class NODE_POOL {
public:
   NODE_POOL            (void)
      : usedNodes(AP_CL)
   {}

   T *                  Alloc                (void) { return policy.Alloc(usedNodes); }

   template <class T1>
   T *                  Alloc                (const T1 & t1) { return policy.Alloc(t1, usedNodes); }

   template <class T1, class T2>
   T *                  Alloc                (const T1 & t1, const T2 & t2) { return policy.Alloc(t1, t2, usedNodes); }

   void                 Delete               (T * ptr) { policy.Delete(ptr, usedNodes); }
   void                 Free                 (void) { policy.Free(); }

   T *                  operator []          (int index) { return usedNodes[index]; }
   const T *            operator []          (int index) const { return usedNodes[index]; }

   bool                 IsEmpty              (void) const { return usedNodes.IsEmpty(); }
   int                  Length               (void) const { return usedNodes.Length(); }

private:
   NODE_POOL(const NODE_POOL & p);
   void operator = (const NODE_POOL & p);

private:
   dsVECTOR<T *>        usedNodes;
   ALLOC_POLICY<T>      policy;
};

class FIXED_SIZE_ALLOCATOR {
public:
   FIXED_SIZE_ALLOCATOR    (void) {}
   ~FIXED_SIZE_ALLOCATOR   (void);

   template <class T>
   T *                     Alloc                   (void);

   template <class T, class V>
   T *                     Alloc                   (const V & p); // copy constructor

   template <class T>
   void                    Free                    (T * ptr);

   template <class T>
   T *                     AllocAlign              (int align);

   template <class T>
   void                    FreeAlign               (T * ptr, int align);

   template <class T>
   T *                     AllocArray              (int count);

   template <class T>
   void                    FreeArray               (T * ptr, int count);

public:
   struct ITEM {
      ITEM * next;
   };

   struct POOL;

   struct CHUNK {
      int                  empty;
      ITEM *               freeItem;
      BYTE *               data;

      inline bool          IsBelong                (void * ptr, POOL * pool) const;

      bool                 operator <              (const CHUNK & p) const {
         if (empty == 0 && p.empty > 0) {
            return false;
         }
         if (empty > 0 && p.empty == 0) {
            return true;
         }

         return empty < p.empty;
      }

      CHUNK(void)
         : empty(0)
         , freeItem(NULL)
         , data(NULL)
      {}
   };

   struct POOL {
      int                  itemSize;
      int                  itemsPerChunk;
      int                  allocated;
      int                  empty;

      dsVECTOR<CHUNK>      fullChunks;
      dsVECTOR<CHUNK>      chunks;

      POOL(void)
         : itemSize(0)
         , itemsPerChunk(0)
         , allocated(0)
         , empty(0)
         , chunks(AP_CL)
         , fullChunks(AP_CL)
      {}

      void                 PrepareNextChunk        (void);
      CHUNK *              FindChunk               (dsVECTOR<CHUNK> & chunks, void * ptr);
   };

private:
   void *                  _Alloc                  (int size);
   void                    _Free                   (void * ptr, int size);

   CHUNK *                 _AllocChunk             (POOL & pool);
   void                    _FreeChunk              (CHUNK & chunk);

private:
   osLOCK                  lock;

public:
   dsVECTOR<POOL>          pools;
};

#if USE_FIXED_ALLOC
extern FIXED_SIZE_ALLOCATOR FixedAlloc;
#endif

}

//
// Pool allocator
//

#include "ds_allocator.hpp"

#endif // _DS_ALLOCATOR_H_
